﻿﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace NetworkSimulator
{
    public abstract class Routing
    {
        protected Topology map = Topology.instance();

        // Use this to call a node quickly by ID
        protected Dictionary<int, Node> nodes;

        // A list of ingress - egress pair
        protected IEList ieList = IEList.instance();

        // Use for prevent make change in map while processing
        protected Dictionary<Link, double> usable_bw;
        protected Dictionary<Link, double> using_bw;
        protected Dictionary<Link, double> cost;

        //use to run offline phase of POOA - RRATE
        public OfflinePhase_RRATE offline_RRATE = OfflinePhase_RRATE.instance();

        public Routing()
        {
            nodes = new Dictionary<int, Node>();
            foreach (Node node in map.Nodes)
            {
                nodes[node.Id] = node;
            }
            usable_bw = new Dictionary<Link, double>();
            using_bw = new Dictionary<Link, double>();
            cost = new Dictionary<Link, double>();
            this.Renew();
        }

        protected void Renew()
        {
            foreach (Node node in map.Nodes)
            {
                foreach (Link link in node.Links)
                {
                    if (link.IsOff)
                        usable_bw[link] = 0;
                    else
                        usable_bw[link] = link.ResidualBandwidth;

                    using_bw[link] = 0;
                    cost[link] = 1;
                }
            }
        }

        // Remove links with bandwidth less than bw
        protected void removeLinks(double bw)
        {
            foreach (Node node in map.Nodes)
                foreach (Link link in node.Links)
                    if (link.ResidualBandwidth < bw || link.IsOff)
                        usable_bw[link] = 0;
        }



        /*******************************************************************
         *  BFS
         *  
         *  CODER:  HOANG CHUNG HIEN
         *  DATE:   27/3/2013
         *  VERSION: 1.0
         *  
         *******************************************************************/
        protected Path BFS(Node source, Node dest)
        {
            Path result_path = new Path();

            Node curNode; // use for browse map

            // queue use for browse from source node to find out dest node
            Queue<Node> queue = new Queue<Node>();

            // tracking use for record browsed link
            Stack<Link> tracking = new Stack<Link>();

            // found or not dest node
            bool found = false;

            // checked node
            Dictionary<Node, bool> checked_node = new Dictionary<Node, bool>();
            foreach (Node node in map.Nodes)
            {
                checked_node.Add(node, false);
            }

            // Add source node to queue
            queue.Enqueue(source);

            // Find out destination node..
            while (queue.Count > 0 && !found)
            {
                curNode = queue.Dequeue();
                foreach (Link link in curNode.Links)
                {
                    if (usable_bw[link] > 0 && !checked_node[link.Destination])
                    {
                        // Track this link
                        tracking.Push(link);

                        if (link.Destination == dest)
                        {
                            found = true;
                            break;
                        }
                        else
                        {
                            // Checked neighbor node
                            checked_node[link.Destination] = true;

                            // Add neighbor to queue
                            queue.Enqueue(link.Destination);
                        }
                    }
                }
            }


            // Get the invert path from tracking
            if (tracking.Count > 0)
            {
                Link now = tracking.Pop();
                Stack<Link> temp = new Stack<Link>();
                temp.Push(now);
                Link next;

                while (tracking.Count > 0)
                {
                    next = tracking.Pop();
                    if (now.Source == next.Destination)
                    {
                        now = next;
                        temp.Push(now);
                    }
                }

                // Get the path from invert path in temp stack
                while (temp.Count > 0)
                {
                    result_path.Links.Add(temp.Pop());
                }
            }
            return result_path;
        }
    //============================================================================


        /*******************************************************************
         *  DIJKSTRA
         *  
         *  CODER:  NGUYEN VAN LIEP
         *  DATE:   ??/??/????
         *  CUSTOMIZE BY: HOANG CHUNG HIEN
         *  CUSTOM DATE: 30/3/2013
         *  VERSION: 1.0
         *  
         *******************************************************************/
        public Path dijkstra(Node source, Node dest)
        {
            int n = map.Nodes.Count;
            double[] d = new double[n];
            int[] pre = new int[n];
            var s = source.Id;

            // Initialize
            for (int v = 0; v < n; v++)
            {
                d[v] = double.MaxValue;
                pre[v] = s;
            }

            d[s] = 0;
            List<Node> T = new List<Node>(map.Nodes);

            while (T.Count > 0)
            {
                // Find node u within T set, where d[u] = min{d[z]:z within T set}
                int u = T[0].Id;
                foreach (Node node in T)
                    if (d[node.Id] < d[u])
                        u = node.Id;

                T.Remove(map.Nodes[u]);

                // Browse all adjacent node to update distance from s.
                foreach (Link link in map.Nodes[u].Links)
                {
                    int v = link.Destination.Id;
                    if (d[v] > d[u] + cost[link])
                    {
                        d[v] = d[u] + cost[link];
                        pre[v] = u;
                    }
                }
            }


            // Get path
            Node destination = dest;
            Node pointer = nodes[pre[destination.Id]];           
            Path result = new Path();
            while (destination != source )
            {
                foreach (Link link in pointer.Links)
                {
                    if (link.Destination == destination)
                    {
                        result.Add(link);
                        destination = nodes[pre[destination.Id]];
                        pointer = nodes[pre[destination.Id]];
                        break;
                    }
                }
            }
            if (!result.isEmpty())
                result.Reverse();

            return result;
        }
    //============================================================================


        protected List<Path> getShortestPaths(Node source, Node dest)
        {
            // Get a min hop number
            int minhop = BFS(source, dest).Links.Count;

            // Result path
            List<Path> r_paths = new List<Path>();

            // Use while generate temporary tree node
            Dictionary<Node, List<Link>> Tree = new Dictionary<Node, List<Link>>();
            // Use for tracking visited node
            Dictionary<Node, bool> visited_node = new Dictionary<Node, bool>();
            // User for tracking visited link
            Dictionary<Link, bool> visited_link = new Dictionary<Link, bool>();

            //
            // Generate Tree by source & map
            //

            // Use while browse map
            Queue<Link> link_queue = new Queue<Link>();
            Dictionary<Node, int> node_father = new Dictionary<Node, int>();
            Dictionary<Node, int> node_level = new Dictionary<Node, int>();
            //
            // Initialize for process tree
            foreach (Node n in map.Nodes)
            {
                node_father[n] = -1;
                node_level[n] = int.MaxValue;
                Tree[n] = new List<Link>();
                visited_node[n] = false;
                foreach (Link l in n.Links)
                    visited_link[l] = false;
            }
            node_level[source] = 0;
            foreach (Link link in source.Links)
            {
                Tree[source].Add(link);
                link_queue.Enqueue(link);
                node_father[link.Destination] = source.Id;
                node_level[link.Destination] = 0;
                visited_node[link.Destination] = true;
                visited_link[link] = true;
            }
            //
            // Process tree
            while (link_queue.Count > 0)
            {
                Link link = link_queue.Dequeue();
                foreach (Link l in link.Destination.Links)
                {
                    // If a link is removed (determine by usable_bw[link] = 0) don't process it to tree
                    if (usable_bw[l] <= 0)
                        continue;

                    // If destination node isn't brother, and destination node isn't father node
                    // and destination node isn't brother of father
                    if (node_father[link.Destination] != node_father[l.Destination]
                        && l.Destination != link.Source
                        && node_level[l.Destination] > node_level[link.Destination])
                    {
                        // If a link isn't added to Tree (or isn't visited), add it and set visited is true
                        if (!visited_link[l])
                        {
                            Tree[link.Destination].Add(l);
                            visited_link[l] = true;
                        }
                        // Add information about node father for prevent go back link
                        node_father[l.Destination] = l.Source.Id;

                        // Tracking is a node visited
                        if (!visited_node[l.Destination])
                            node_level[l.Destination] = node_level[link.Destination] + 1;

                        link_queue.Enqueue(l);
                        //System.Threading.Thread.Sleep(1500);
                        //Console.WriteLine(node_father[l.Destination] + "-" + link.Source.ID);
                        //Console.WriteLine(l.Source.ID + "-" + l.Destination.ID);
                    }
                }

                if (!visited_node[link.Destination])
                    visited_node[link.Destination] = true;

                //Console.WriteLine(link.Source.ID + " : " + link.Destination.ID + "    L " + link.Destination.ID + " : " + 
                //    node_father[link.Destination]);
                //Console.WriteLine(node_father[link.Destination]);
            }

            //
            // Generate paths by Tree
            //

            // Use for deepth first search
            Stack<Link> link_stack = new Stack<Link>();
            //
            // Use for tracking a new path
            Stack<Link> temp_path = new Stack<Link>();

            //
            // Get first link from source node
            foreach (Link link in Tree[source])
            {
                link_stack.Push(link);
            }
            while (link_stack.Count > 0)
            {
                Link link = link_stack.Pop();

                // While a path found, go back by pop out link for store other path
                while (temp_path.Count > 0 && temp_path.Peek().Destination != link.Source)
                    temp_path.Pop();
                //
                // Continue to get new path
                temp_path.Push(link);
                foreach (Link l in Tree[link.Destination])
                {
                    link_stack.Push(l);
                }

                // If destination is found
                if (link.Destination == dest)
                {
                    //
                    // Create a new path for hold links
                    Path path = new Path();
                    // 
                    // Create a stack for get link from invert links
                    Stack<Link> temp = new Stack<Link>();
                    //
                    // Get invert link from temp_path
                    foreach (Link li in temp_path)
                    {
                        temp.Push(li);
                    }
                    //
                    // OK, now get path
                    while (temp.Count > 0)
                    {
                        Link l = temp.Pop();
                        path.Links.Add(l);
                    }
                    // Store it if number of hop not higher than minhop
                    if (path.Links.Count == minhop)
                        r_paths.Add(path);

                }
            }

            return r_paths;
            //public Path 

        }
    //==============================================================================

        /*******************************************************************
         *  GET CRITICAL LINKS
         *  
         *  Input: Node source, Node destination
         *  Output: A List of critical links
         *  
         *  CODER:  HOANG CHUNG HIEN
         *  DATE:   27/3/2013
         *  VERSION: 1.0
         *  
         *******************************************************************/
        protected List<Link> getCriticalLinks(Node source, Node dest)
        {
            this.Renew();
            return FordFulkerson(source, dest);
        }

        private List<Link> FordFulkerson(Node source, Node dest)
        {

            double flow = 0;
            double min_capacity = double.MaxValue;
            Path path = BFS(source, dest);

            // Process max flow
            while (path != null && path.Links.Count > 0)
            {
                foreach (Link link in path.Links)
                {
                    if (min_capacity > usable_bw[link])
                        min_capacity = usable_bw[link];
                }
                if (min_capacity == double.MaxValue)
                    throw new Exception("Min capacity: " + min_capacity);

                AugmentPath(path, min_capacity);
                flow += min_capacity;

                path = BFS(source, dest);
            }

            // Return the mincut set
            return FindMinCut(source);
        }
        private void AugmentPath(Path path, double min_capacity)
        {
            foreach (Link link in path.Links)
            {
                using_bw[link] += min_capacity;
                usable_bw[link] -= min_capacity;
            }
        }
        private List<Link> FindMinCut(Node source)
        {
            Queue<Node> queue = new Queue<Node>();
            List<Node> discovered = new List<Node>();
            List<Link> minCutEdges = new List<Link>();
            List<Node> minCutNodes = new List<Node>();
            queue.Enqueue(source);

            while (queue.Count > 0)
            {
                Node current = queue.Dequeue();
                if (discovered.Contains(current))
                    continue;
                minCutNodes.Add(current);
                discovered.Add(current);

                var edges = current.Links;
                foreach (var edge in edges)
                {
                    var next = edge.Destination;
                    if (usable_bw[edge] <= 0 || discovered.Contains(next))
                        continue;
                    queue.Enqueue(next);
                    minCutEdges.Add(edge);
                }
            }

            var minCutResult = new List<Link>();

            foreach (var item in minCutNodes)
            {
                var edges = item.Links;
                foreach (var edge in edges)
                {
                    if (minCutNodes.Contains(edge.Destination))
                        continue;
                    if (edge.ResidualBandwidth > 0 && !minCutEdges.Contains(edge))
                        minCutResult.Add(edge);
                }
            }

            return minCutResult;
        }
    //==============================================================================
        //Added by Dung
        protected double FindMaxFlow(Node source, Node dest, List<Path> result)
        {
            double flow = 0;
            double min_capacity = double.MaxValue;
            Path path = BFS(source, dest);

            // Process max flow
            while (path != null && path.Links.Count > 0)
            {
                foreach (Link link in path.Links)
                {
                    if (min_capacity > usable_bw[link])
                        min_capacity = usable_bw[link];
                }
                if (min_capacity == double.MaxValue)
                    throw new Exception("Min capacity: " + min_capacity);

                path.cost = min_capacity;

                result.Add(path);

                AugmentPath(path, min_capacity);
                flow += min_capacity;

                path = BFS(source, dest);
            }

            //return Maxflow
            return flow;
        }


        public abstract Path getPath(Request req);

    }
}

